/*
 * binaryheap.c
 *
 *  Created on: Jun 17, 2010
 *      Author: Guilherme
 */

#include "binaryheap.h"

PriorityQueue init(int maxElements) {
	PriorityQueue Q;

	if ((Q = malloc(sizeof(struct heapstruct))) == NULL) {
		fprintf(stderr, "Could not allocate memory for a new Priority Queue");
		exit(2);
	}
	if ((Q->nodes = calloc(maxElements + 1, sizeof(struct heapnode *))) == NULL) {
		fprintf(stderr, "Could not allocate memory for Heap nodes");
		exit(2);
	}
	if ((Q->positions = calloc(maxElements + 1, sizeof(int))) == NULL) {
		fprintf(stderr, "Could not allocate memory for Heap positions");
		exit(2);
	}

	HeapNode n;
	if ((n = malloc(sizeof(struct heapnode))) == NULL) {
		fprintf(stderr, "Could not allocate memory for a new heap node");
		exit(2);
	}
	Q->capacity = maxElements + 1;
	Q->size = 0;
	Q->nodes[0] = n;
	Q->nodes[0]->nodeID = 0;
	Q->nodes[0]->distance = INT_MIN;
	Q->positions[Q->nodes[0]->nodeID] = 0;

	return Q;
}

void insert(HeapNode node, PriorityQueue Q) {
	int hole;

	if (isFull(Q)) {
		fprintf(stderr, "Could not add a new element %d to the heap. Heap is full!", node->nodeID);
		exit(2);
	}
	for (hole = ++Q->size; Q->nodes[hole / 2]->distance > node->distance; hole /= 2) {
		Q->nodes[hole] = Q->nodes[hole / 2];
		Q->positions[Q->nodes[hole / 2]->nodeID] = hole;
	}
	Q->nodes[hole] = node;
	Q->positions[node->nodeID] = hole;
}

HeapNode deleteMin(PriorityQueue Q) {
	HeapNode minItem = findMin(Q);
	Q->nodes[1] = Q->nodes[Q->size--];
	Q->positions[Q->nodes[1]->nodeID] = 1;
	percolateDown(1, Q);

	return minItem;
}

HeapNode findMin(PriorityQueue Q) {
	if (isEmpty(Q)) {
		fprintf(stderr, "Could not find min element. Heap is empty!");
		exit(2);
	}
	return Q->nodes[1];
}

void decreaseKey(HeapNode node, PriorityQueue Q) {
	int n;

	n = Q->size;
	Q->size = Q->positions[node->nodeID] - 1;
	insert(node, Q);
	Q->size = n;
}

void destroy(PriorityQueue Q) {
	free(Q->nodes);
	free(Q->positions);
	free(Q);
}

void makeEmpty(PriorityQueue Q) {
    Q->size = 0;
}

int isEmpty(PriorityQueue Q) {
    return Q->size == 0;
}

int isFull(PriorityQueue Q) {
	return Q->size == Q->capacity;
}

void print_heap(PriorityQueue Q) {
	int i;

	for (i = 1; i <= Q->size; i++)
		printf(" %d ", Q->nodes[i]->nodeID);
	printf("\n");
}

void percolateDown(int hole, PriorityQueue Q) {
	int child;
	HeapNode tmp;

	tmp = Q->nodes[hole];

	for (child = 0 ; hole * 2 <= Q->size; hole = child) {
		child = hole * 2;
		if (child != Q->size && Q->nodes[child + 1]->distance < Q->nodes[child]->distance) {
			child++;
		}
		if (Q->nodes[child]->distance < tmp->distance) {
			Q->nodes[hole] = Q->nodes[child];
			Q->positions[Q->nodes[child]->nodeID] = hole;
		} else {
			break;
		}
	}
	Q->nodes[hole] = tmp;
	Q->positions[tmp->nodeID] = hole;
}

/*int main(int argc, char **argv) {
	PriorityQueue Q;
	int i, j;

    Q = init(1000);
	for (i = 0, j = 1000 / 2; i < 1000; i++, j = (j + 71) % 1000) {
		HeapNode n;
		if ((n = malloc(sizeof(struct heapnode))) == NULL) {
			fprintf(stderr, "Could not allocate memory for a new heap node");
		}
		n->nodeID = i;
		n->distance = j;
		insert(n, Q);
		fprintf(stdout, "Added, %d\n", j);
	}

	j = 0;
	while (!isEmpty(Q)) {
		if (deleteMin(Q)->distance != j++) {
			fprintf(stderr, "Error in DeleteMin, %d\n", j);
		} else {
			fprintf(stdout, "Success in DeleteMin, %d\n", j);
		}
	}

	printf("Done...\n");

	return 0;
}*/

